import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class RandomizedQueue<Item> implements Iterable<Item> {

	private int size = 0;
	private int head = 0;
	private int tail = 0;
	private Item[] q;

	public RandomizedQueue() {
		q = (Item[]) new Object[2];
	}

	public boolean isEmpty() {
		return size == 0;
	}

	public int size() {
		return size;
	}

	public void enqueue(Item item) {
		if (item == null) {
			throw new NullPointerException();
		}
		if (tail >= q.length) {
			resize(2 * q.length);
		}
		q[tail] = item;
		tail++;
		size++;
	}

	public Item dequeue() {
		if (isEmpty()) {
			throw new NoSuchElementException();
		}
//		int uniform = StdRandom.uniform(size);
		Item item = q[head];
		q[head] = null;
		head++;
		size--;
		if (size > 0 && size == q.length / 4) {
			resize(q.length / 2);
		}
		return item;
	}

	// return (but do not delete) a random item
	public Item sample() {
		if (isEmpty()) {
			throw new NoSuchElementException();
		}
		int uniform = StdRandom.uniform(head, tail);
		return q[uniform];
	}

	// return an independent iterator over items in random order
	public Iterator<Item> iterator() {
		return new RandomizedQueueIterator();
	}

	private void resize(int capacity) {
		Item[] temp = (Item[]) new Object[capacity];
		int end = head + size;
		int index = 0;
		for (int i = head; i < end; i++) {
			temp[index] = q[i];
			index++;
		}
		q = temp;
		head = 0;
		tail = head + size;
	}

    private class RandomizedQueueIterator implements Iterator<Item> {
    	int index = 0;
        Item[] iq;

        public RandomizedQueueIterator() {
    		iq = (Item[]) new Object[size];
    		int index = 0;
    		for (int x = head; x < tail; x++) {
    			iq[index] = q[x];
    			index++;
    		}
            StdRandom.shuffle(iq);
        }

        public boolean hasNext() {
        	return index < iq.length;
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }

        public Item next() {
            if (!hasNext()) {
            	throw new NoSuchElementException();
            }
            Item item = iq[index];
            index++;
            return item;
            
        }

		@Override
		public String toString() {
			return "RandomizedQueueIterator [iq=" + Arrays.toString(iq) + "]";
		}
    }
    
}